#include<iostream>
#include<cstdlib>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;

//原文链接：https://blog.csdn.net/qq_41884662/article/details/115265151

struct TreeNode {
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};


class Solution {
//private:
//    vector<vector<int>> res;
//    vector<int> rec;
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        if (root == NULL) {
            return ans;
        }
        queue<TreeNode*> q;
        q.push(root);  //push,不是push_back
        bool isLeft = false;
        while (!q.empty()) {
            int rowLen = q.size();
            vector<int> temp;
            for (int i = 0; i < rowLen; ++i) {
                TreeNode* curNode = q.front();
                q.pop();
                if (curNode != NULL) {
                    temp.push_back(curNode->val);
                    if (curNode->left)q.push(curNode->left);
                    if (curNode->right)q.push(curNode->right);
                }
            }
            isLeft = !isLeft; //偶数行反过来输出（右到左），题目要求的
            if (!isLeft) {
                ans.push_back(vector<int>(temp.rbegin(), temp.rend())); //取代了reverse,提升了运行速度
            }
            else {
                ans.push_back(temp);
            }
        }
        return ans;
    }
};


int main() {
    TreeNode* x1 = new TreeNode(1);
    TreeNode* x2 = new TreeNode(2);
    TreeNode* x3 = new TreeNode(3);
    TreeNode* x4 = new TreeNode(4);
    TreeNode* x5 = new TreeNode(5);
    TreeNode* x6 = new TreeNode(6);
    TreeNode* x7 = new TreeNode(7);
    x1->left = x2;
    x1->right = x3;
    x2->left = x4;
    x2->right = x5;
    x3->left = x6;
    x3->right = x7;
    Solution* x = new Solution;
    vector<vector<int>> res;
    res = x->levelOrder(x1);
    for (int i = 0; i < res.size(); i++) {
        for (int j = 0; j < res[i].size(); j++) {
            cout << res[i][j] << " ";
        }
        cout << endl;
    }

    system("pause");
    return 0;
}

